package com.itheima.leetcode.od.c.bf;

import java.util.Arrays;
import java.util.Scanner;

/**
 * <h3>叠积木</h3>
 */
public class StackingBlocks {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Integer[] nums = Arrays.stream(sc.nextLine().split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        System.out.println(getResult(nums));
    }

    public static int getResult(Integer[] nums) {
        int n = nums.length;

        // 如果只有一个积木，那么只能是一层高度
        if (n == 1) {
            return 1;
        }

        // 如果有两个积木
        if (n == 2) {
            // 如果两个积木长度相同，则最大高度为2
            // 如果两个积木长度不同，则最大高度为1
            return nums[0] - nums[1] != 0 ? 1 : 2;
        }

        // 积木按长度降序
        Arrays.sort(nums, (a, b) -> b - a);

        // 一层的最小长度，即最长的积木的长度
        int minLen = nums[0];
        // 一层的最大长度
        int maxLen = nums[0] + nums[nums.length - 1];

        // 尝试 minLen 和 maxLen 中每一个值作为一层长度
        for (int len = minLen; len <= maxLen; len++) {
            // 对应一层长度限制下的最大高度
            int height = 0;

            // 通过l,r指针去选择组成一层的一个或两个积木
            // l指针指向最大长度的积木
            int l = 0;
            // r指针指向最小长度的积木
            int r = n - 1;

            // 如果最大长度的积木，可以独立一层，则l++，height++
            while (l < n && nums[l] == len) {
                l++;
                height++;
            }

            // 如果 l,r积木无法组成一层
            // 假设nums[l] + nums[r] > length，则必然nums[l] + nums[r-1] > length，
            // 因为nums已降序，nums[r-1] >= nums[r]，即必然l积木无法和其他积木组成一层
            // 假设nums[l] + nums[r] < length，则必然nums[l+1] + nums[r] < length，
            // 因为nums已降序，nums[l+1] <= nums[l]，即必然r积木无法和其他积木组成一层
            while (l < r) { // 有点像两数之和
                if (nums[l] + nums[r] != len) {
                    break;
                }

                l++;
                r--;
                height++;
            }

            // 如果正常结束，则必然l > r，否则就是异常结束
            if (l <= r) {
                continue;
            }

            return height;
        }

        return -1;
    }
}